package com.wfm.leetcode.editor.cn;

import com.wfm.common.ListNode;
import org.junit.Test;

/**
 * 比如 left =4 ，right = 6
 * dummy->head
 *          1->  2  ->  3  -> 4  -> 5->  6->  7->  8->null
 *                    pre   start       end  next
 *  需要四个指针:为了翻转start-end，需要定位到pre，并且保存next
 *
 */
public class BM2链表内指定区间翻转92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode();
        dummy.next=head;
        ListNode pre = dummy;
        for (int i = 0; i < left-1; i++) {
            pre = pre.next;
        }
        ListNode end = pre;
        for (int i = 0; i < right-left+1; i++) {
            end = end.next;
        }
        ListNode next = end.next;
        ListNode start = pre.next;
        pre.next = null;
        end.next = null;
        new BM1翻转链表24().reverseList(start);
        pre.next = end;
        start.next = next;
        return dummy.next;
    }
    public ListNode reverseBetween1(ListNode head, int left, int right) {
        ListNode dummy = new ListNode();
        dummy.next=head;
        ListNode pre = dummy;
        ListNode next = dummy;
        while (pre!=null&&--left>0){
            pre=pre.next;
        }
        while (next!=null&&right-->0){
            next=next.next;
        }
        ListNode tmp = next.next;
        next.next = null;
        new BM1翻转链表24().reverseList(pre.next);
        pre.next.next=tmp;
        pre.next=next;

        return dummy.next;
    }
    @Test
    public void test2(){
        ListNode listNode = ListNode.generalListNode(new int[]{1, 2, 3, 4, 5});
        ListNode listNode1 = reverseBetween1(listNode, 2, 4);
        ListNode.printListNode(listNode1);
    }
    @Test
    public void test(){
        ListNode head = new ListNode(1);
        for (int i = 2; i < 9; i++) {
            ListNode n = new ListNode(i);
            ListNode.addNodeTail(head,n);
        }
        ListNode listNode = reverseBetween(head, 4, 6);
        ListNode.printListNode(listNode);
    }
}
